﻿namespace AlgorithmInterview.Chapter02._09;

/// <summary>
/// 从给定的车票中找出旅程的路线
/// </summary>
public class Itinerary
{
    private static void PrintResult(Dictionary<string, string> input)
    {
        // 用来存储把input的键和值调换后的信息
        Dictionary<string, string> reverseImput = new Dictionary<string, string>();
        foreach (var item in input)
        {
            reverseImput.Add(item.Value, item.Key);
        }

        string start = null;
        // 找到起点
        foreach (var item in input)
        {
            if (!reverseImput.ContainsKey(item.Key))
            {
                start = item.Key;
                break;
            }
        }

        if (start == null)
        {
            Console.WriteLine("输入不合法");
            return;
        }

        // 从起点出发按照顺序遍历路径
        string to = input[start];
        Console.Write(start + " -> " + to);
        start = to;
        to = input[to];
        while (to != null)
        {
            Console.Write("," + start + " -> " + to);
            start = to;
            if (input.ContainsKey(to))
            {
                to = input[to];
            }
            else
            {
                to = null;
            }
        }
    }


    public void Main(String[] args)
    {
        Dictionary<string, string> input = new Dictionary<string, string>();
        input.Add("西安", "成都");
        input.Add("北京", "上海");
        input.Add("大连", "西安");
        input.Add("上海", "大连");

        PrintResult(input);

        Console.ReadLine();
    }
}